The present invention relates generally to methods for authenticating a channel, and more particularly to a method for authenticating a channel in a large-scale distributed system.
Enforcing access controls in any computer system generally requires that sources of access requests (or more generally messages) be determined. In a computer system, a message is usually received on a channel, such as a network. Determining the set of principals (e.g., users, processes, or computers) that could have initiated that message is known as "authenticating the channel" (or request). Prior to acting on a request or forwarding a message, a computer system or operator usually wants to authenticate the channel.
The authentication process in centralized computer systems is simplified by the fact that there is a central authority (the operating system, or a security kernel thereof) that controls all channels and knows which principals can initiate requests on which channels. In a distributed system, however, typically no such central authority exists for this information. As the distributed system gets larger and more diverse, the difficulty of reliably authenticating a channel increases substantially. An in a system as large and diverse as the Internet, reliably authenticating a channel presents a heretofore impossibly complicated task.
As an example, consider a system in which the channel is the public key that can be used to verify the signature on the message, and authenticating the channel means determining the set of principals that could have generated that signature. Lacking a global authority on this information, the user is asked to defer to a "path" of channels c.sub.1, . . . , c.sub.k (i.e., other public keys) such that: (i) the user believes it can authenticate c.sub.i, (ii) each c.sub.i, i&lt;k, has uttered a statement (a certificate) regarding for what principal c.sub.i+1 speaks, and (iii) c.sub.k has uttered a statement regarding for what principal the channel of interest to the user speaks. If the user is willing to trust the statements of each channel on the pat then the user authenticates the target channel according to the statement that c.sub.k made about it.
This technique relies on a single path of channels. Relying on a single path of channels can be very unreliable, however, since it assumes trust in all intermediate channels on the path, and a single instance of misplaced trust can result in a false authentication of the target channel. That is, if any c.sub.i in the path provides a false statement regarding c.sub.i+1, either accidentally or intentionally, then proper semantics for the target channel have not been achieved.
To attempt to solve the problem of gaining increased assurance in the authentication process, some have suggested using multiple paths of channels to overcome the single point of failure in the above approach. These path authentication methods assign numerical measures of trustworthiness to paths or collections of paths. These efforts also observe that shorter paths and multiple paths lend additional credibility to the authentication of a channel, and the derived numerical measures tend to reflect those observations. Yet, these efforts do not disclose how to find the paths for use as input to the evaluation functions, but merely that doing so will improve the authentication process.
Methods exist for locating a single path to a channel, but in so doing they assume a known "topology" regarding what channels make statements about others. Other path authentication methods for finding a single path to a channel exhibit exponential worst-case complexity as a function of the number of channels and statements. Thus, known path authentication methods either do not look beyond a single path, assume a known topology on the relationships between channels or suffer from exponential complexity as the number of channels and statements increases.
N. McBurnett, "PGP Web of Trust Statistics," which can be found at http://bcn.boulder.co.us/.about.neal/pgpstat/, 1996, is an effort to gather statistics about the graph of channels (i.e., public keys) induced by PGP certificates worldwide. This work focuses on characterizing the structure of the graph, and in particular identifying its strongly-connected components, determining mean and maximum shortest path distances between channels, and identifying channels in the graph that are central to its connectivity. While useful, this work is unable to increase the assurance in authentication of any channel of interest, but rather simply characterizes the graph and cannot locate paths of channels.
One known technique for increasing the assurance in channel authentication is to limit the length of the path used, thereby limiting the number of intermediate principals that must be trusted. While this technique increases the assurance, by itself it is not sufficient to achieve the desired levels of assurance since it maintains the single point failure of the earlier mentioned systems.
A second known technique for increasing the assurance in channel authentication is to employ multiple paths, and to authenticate the target channel based upon information obtained via each of these paths. As in the above, by itself this technique cannot provide the desired levels of assurance because there is no guarantee that the same single point failure does not appear in multiple paths, thereby providing a false sense of security.
The present invention is therefore directed to the problem of developing a method and system for reliably authenticating a channel in a large distributed system, such as the Internet, which does not assume a known topology of the system and does not exhibit exponential worst case complexity.